/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package Controller;

import Exceptions.ElementAlreadyExistsException;
import Exceptions.ElementNotFoundException;
import Exceptions.EmptyTreeException;
import java.util.LinkedList;

/**
 *
 * @author asouza, subx
 */
public class AVLTree<T extends Comparable<T>, K> {
    /**
     * Referência para a raiz da árvore;
     */
    private AVLNode root;
    private AVLNode terminal = new AVLNode();


    public AVLTree(){
        setRoot(terminal);
    }
    
    /**
     * Imprimir a arvore em ordem.
     * @param node - Nó onde a impressão se iniciará.
     */

    public void printAVL (AVLNode<T, K> node) {
        if (!(node.getLeft().isTerminal()))
            printAVL(node.getLeft());
        System.out.println(node.getKey());
        if (!(node.getRight().isTerminal()))
        printAVL(node.getRight());
    }

    /**
     * Transforma a arvore em uma LinkedList.
     * @return LinkedList derivada da arvore.
     */

    public LinkedList<K> toList (AVLNode<T, K> node) {
        LinkedList<K> list = new LinkedList<K>();
        return toListAux(node, list);
    }

    private LinkedList<K> toListAux (AVLNode<T, K> node, LinkedList<K> list) {
        if (!(node.getLeft().isTerminal()))
            toListAux(node.getLeft(), list);
        list.add(node.getRef());
        if (!(node.getRight().isTerminal()))
            toListAux(node.getRight(), list);
        return list;
     }

    /**
     * Busca em ávore binária.
     * @param key Chave que se deseja buscar na árvore.
     * @throws ElementNotFoundException
     * @throws EmptyTreeException
     */
    public AVLNode search(T key) throws ElementNotFoundException, EmptyTreeException {
        AVLNode pt = getRoot();
        try {
            return auxSearch(key, pt);
        } catch (ElementNotFoundException a) {
            throw a;
        } catch (EmptyTreeException b) {
            throw b;
        }

    }

    /**
     * Busca em ávore binária.
     * @param key Chave que se deseja buscar na árvore.
     * @param pt Aponta a raiz da árvore
     */

    private AVLNode auxSearch(T key, AVLNode<T, K> pt) throws ElementNotFoundException, EmptyTreeException {
        if(pt.isTerminal()){
            throw new EmptyTreeException();
        }else if(pt.getKey().compareTo(key) == 0){
            return pt;
        }else if(pt.getKey().compareTo(key) > 0){
            if(pt.getLeft().isTerminal()){
                throw new ElementNotFoundException();
            }else{
                pt = pt.getLeft();
                return auxSearch(key, pt);
            }
        }else if(pt.getRight().isTerminal()){
            throw new ElementNotFoundException();
        }else{
            pt = pt.getRight();
            return auxSearch(key, pt);
        }
    }

    /**
     * Insere o elemento especificado na árvore, rebalanceando-a.
     * @param key Chave identificadora do nó.
     * @param ref Referência para a informação que se deseja armazenar.
     * @throws ElementAlreadyExistsException
     */

    private boolean h = false;

    public void insert (T key, K ref) throws ElementAlreadyExistsException {
        try {
            h = false;
            root = auxInsert(key, ref, root);
        } catch (ElementAlreadyExistsException b) {
            throw b;
        }

    }

    private AVLNode auxInsert(T key, K ref, AVLNode<T, K> aux) throws ElementAlreadyExistsException {
        if(aux.isTerminal()){
            aux = new AVLNode(key, ref, terminal, terminal);
            h = true;
        }else if(aux.getKey().compareTo(key) == 0){
            throw new ElementAlreadyExistsException("Elemento já existe na árvore!");
        }else if(aux.getKey().compareTo(key) > 0){
            aux.setLeft(auxInsert(key, ref, aux.getLeft()));
            aux.adjustHeight();
            if(h){
                if (aux.getBalanceFactor() == 2 && aux.getLeft().getBalanceFactor() == 1) {
                    aux = rotacaoDireita(aux);
                } else if (aux.getBalanceFactor() == 2 && aux.getLeft().getBalanceFactor() == -1) {
                    aux.setLeft(rotacaoEsquerda(aux.getLeft()));
                    aux = rotacaoDireita(aux);
                } else if (aux.getBalanceFactor() == 0) {
                    h = false;
                }
            }
        }else{
            aux.setRight(auxInsert(key, ref, aux.getRight()));
            aux.adjustHeight();
            if(h){
                if (aux.getBalanceFactor() == -2 && aux.getRight().getBalanceFactor() == -1) {
                    aux = rotacaoEsquerda(aux);
                } else if (aux.getBalanceFactor() == -2 && aux.getRight().getBalanceFactor() == 1) {
                    aux.setRight(rotacaoDireita(aux.getRight()));
                    aux = rotacaoEsquerda(aux);
                }
                else if (aux.getBalanceFactor() == 0) {
                    h = false;
                }
            }
        }
        return aux;
    }

    /**
     * Remove um elemento a partir de sua chave.
     * @param key - Chave a ser removida.
     * @throws ElementNotFoundException
     */

    public void remove(T key) throws ElementNotFoundException, EmptyTreeException {
        try {
            auxRemove (key, root);
        } catch (ElementNotFoundException e) {
            throw e;
        } catch (EmptyTreeException e) {
            throw e;
        }
    }

    private AVLNode<T, K> auxRemove (T key, AVLNode<T, K> node) throws ElementNotFoundException, EmptyTreeException {
        if (node.isTerminal()) {
            throw new EmptyTreeException();
        }
        if (node.isLeaf() && node.getKey().compareTo(key) != 0) {
            throw new ElementNotFoundException();
        } else if (node.getKey().compareTo(key) == 0) {
            if (node.isLeaf()) {
                node = new AVLNode();
            } else if (node.getRight().isTerminal() && !(node.getLeft().isTerminal())) {
                node = node.getLeft();
            } else if (!(node.getRight().isTerminal()) && node.getLeft().isTerminal()) {
                node = node.getRight();
            } else {
                AVLNode<T, K> aux = findMax(node.getLeft());
                node.setKey(aux.getKey());
                node.setRef(aux.getRef());
                aux.setKey(null);
            }
        } else if (node.getKey().compareTo(key) > 0) {
            node.setLeft(auxRemove(key, node.getLeft()));
            node.adjustHeight();
            if (node.getBalanceFactor() == 2 && node.getLeft().getBalanceFactor() == 1) {
                node = rotacaoDireita(node);
            } else if (node.getBalanceFactor() == 2 && node.getLeft().getBalanceFactor() == -1) {
                node.setLeft(rotacaoEsquerda(node.getLeft()));
                node = rotacaoDireita(node);
            } else if (node.getBalanceFactor() == -2 && node.getRight().getBalanceFactor() == -1) {
                node = rotacaoEsquerda(node);
            } else if (node.getBalanceFactor() == -2 && node.getRight().getBalanceFactor() == 1) {
                node.setRight(rotacaoDireita(node.getRight()));
                node = rotacaoEsquerda(node);
            }
        } else {
            node.setRight(auxRemove(key, node.getRight()));
            node.adjustHeight();
            if (node.getBalanceFactor() == 2 && node.getLeft().getBalanceFactor() == 1) {
                node = rotacaoDireita(node);
            } else if (node.getBalanceFactor() == 2 && node.getLeft().getBalanceFactor() == -1) {
                node.setLeft(rotacaoEsquerda(node.getLeft()));
                node = rotacaoDireita(node);
            } else if (node.getBalanceFactor() == -2 && node.getRight().getBalanceFactor() == -1) {
                node = rotacaoEsquerda(node);
            } else if (node.getBalanceFactor() == -2 && node.getRight().getBalanceFactor() == 1) {
                node.setRight(rotacaoDireita(node.getRight()));
                node = rotacaoEsquerda(node);
            }
        }
        return node;
    }

    /**
     * Encontra o maior elemento a partir de certo nó.
     * @param node - Nó no qual a busca deve ser iniciada.
     * @return
     */
    private AVLNode<T, K> findMax (AVLNode<T, K> node) {
        AVLNode<T, K> aux = node;
        while(!aux.getRight().isTerminal()) {
            aux = aux.getRight();
        }
        return aux;
    }

    /**
     * Percorre a árvore, recursivamente, da raiz até as folhas ajustando as
     * alturas.
     * @param pt Referência para a raiz da árvore.
     */
    public void adjustHeights(AVLNode<T, K> pt){
        if(pt.getLeft() != null)
            adjustHeights(pt.getLeft());

        if(pt.getRight() != null)
            adjustHeights(pt.getRight());
        
        if(pt != null)
            pt.adjustHeight();
    }

    /**
     * Retorna uma referência para a raiz da árvore.
     * @return AVLNode 
     */
    public AVLNode getRoot() {
        return root;
    }

    /**
     * Modifica o conteúdo da variável root.
     * @param root
     */
    public void setRoot(AVLNode root) {
        this.root = root;
    }

    /**
     * Verifica se a árover está vazia.
     * @return Retorna verdadeiro em caso positivo e false caso contrário.
     */
    public boolean isEmpty() {
        return getRoot().isTerminal();
    }

    /**
     * Executa a rotação direita na arvore, a partir de um no.
     * @param pt - no a partir do qual a rotação ocorrera
     * @return o no rotacionado
     */

    private AVLNode<T, K> rotacaoDireita(AVLNode pt) {
        AVLNode q = pt.getLeft();
        AVLNode temp = q.getRight();

        q.setRight(pt);
        pt.setLeft(temp);
        return q;
    }

    /**
     * Executa a rotação esquerda na arvore, a partir de um no.
     * @param pt - no a partir do qual a rotação ocorrera
     * @return o no rotacionado
     */

    private AVLNode<T, K> rotacaoEsquerda(AVLNode pt) {
        AVLNode q = pt.getRight();
        AVLNode temp = q.getLeft();

        q.setLeft(pt);
        pt.setRight(temp);
        return q;
    }
    
}
